package Leetcode.树;

/**
 * @ClassName 删除二叉搜索树中的节点
 * @since: 2023/8/20 10:12
 * @auth: kirito
 * @description:
 **/
public class 删除二叉搜索树中的节点 {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 如果根节点为空，直接返回 null
        if (root == null) {
            return null;
        }

        // 如果当前节点的值等于要删除的值 key
        if (root.val == key) {
            // 如果当前节点的左子树为空，直接返回右子树作为新的根节点
            if (root.left == null) {
                return root.right;
            }
            // 如果当前节点的右子树为空，直接返回左子树作为新的根节点
            if (root.right == null) {
                return root.left;
            }

            // 如果当前节点的左右子树都不为空
            TreeNode t = root.left;
            while (t.right != null) {
                t = t.right;
            }
            // 找到当前节点左子树中的最右侧节点 t，将当前节点的右子树连接到 t 的右子树上
            t.right = root.right;
            // 返回当前节点的左子树作为新的根节点
            return root.left;
        } else if (root.val < key) {
            // 如果当前节点的值小于要删除的值 key，在右子树中递归删除
            root.right = deleteNode(root.right, key);
        } else {
            // 如果当前节点的值大于要删除的值 key，在左子树中递归删除
            root.left = deleteNode(root.left, key);
        }

        // 返回更新后的根节点
        return root;
    }

}
